class Solution {
public:
    unordered_map<int, unordered_map<int, pair<int, int>>> dp;
    int tallestBillboard(vector<int>& rods) {
        return dfs(rods.size() - 1, 0, rods);
    }
    int dfs(int i, int k, vector<int>& rods)
    {
        if (i < 0 && k) return -100000;
        else if (i < 0) return 0;
        if (dp[i][k].first) return dp[i][k].second;
        int ans = dfs(i - 1, k, rods);
        ans = max(ans, dfs(i - 1, k + rods[i], rods) + rods[i]);
        ans = max(ans, dfs(i - 1, k - rods[i], rods));
        dp[i][k].first = 1;
        return dp[i][k].second = ans;
    }
};